#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
  static bool cmp(const vector<int> &a, const vector<int> &b) {
    if (abs(a[0] - a[1]) < abs(b[0] - b[1])) {
      return true;
    }
    return false;
  }
  int twoCitySchedCost(vector<vector<int>> &costs) {
    if (costs.empty())
      return 0;
    vector<vector<int>> ac;
    vector<vector<int>> bc;
    unsigned long long res = 0;
    for (int i = 0; i < costs.size(); ++i) {
      if (costs[i][0] < costs[i][1]) {
        ac.push_back(costs[i]);
        res += costs[i][0];
      } else {
        bc.push_back(costs[i]);
        res += costs[i][1];
      }
    }
    if (ac.size() == bc.size()) {
      return res;

    } else if (ac.size() > bc.size()) {
      int cha = (ac.size() - bc.size()) >> 1;
      sort(ac.begin(), ac.end(), cmp);
      for (int i = 0; i < cha; ++i) {
        res += abs(ac[i][0] - ac[i][1]);
      }
      return res;
    } else {
      int cha = (bc.size() - ac.size()) >> 1;
      sort(bc.begin(), bc.end(), cmp);
      for (int i = 0; i < cha; ++i) {
        res += abs(bc[i][0] - bc[i][1]);
      }
      return res;
    }
  }
};

int main() {
  vector<vector<int>> a = {{259, 770}, {448, 54},  {926, 667},
                           {184, 139}, {840, 118}, {577, 469}};
  Solution s;
  int res = s.twoCitySchedCost(a);
  cout << res << endl;
}
